INFORMS JOURNAL ON COMPUTING
Vol. 30, No. 3, Summer 2018, pp. 554–569
http://pubsonline.informs.org/journal/ijoc/ ISSN 1091-9856 (print), ISSN 1526-5528 (online)
The Vehicle Routing Problem with Floating Targets:
Formulation and Solution Approaches
Claudio Gambella,a Joe Naoum-Sawaya,b Bissan Ghaddarb
a IBM Research, Mulhuddart, Dublin 15, Ireland; b Ivey Business School, University of Western Ontario, London, Ontario N6G 0N1, Canada
Contact: claudio.gambella@unibo.it, http://orcid.org/0000-0001-7134-0852 (CG); jnaoumsa@uwaterloo.ca,
http://orcid.org/0000-0002-4908-225X (JN-S); bghaddar@uwaterloo.ca, http://orcid.org/0000-0003-4695-200X (BG)
Received: July 13, 2016
Revised: August 15, 2017
Accepted: November 6, 2017
Published Online: October 2, 2018
https://doi.org/10.1287/ijoc.2017.0800
Copyright: © 2018 INFORMS
Abstract. This paper addresses a generalization of the vehicle routing problem in which
the pick-up locations of the targets are nonstationary. We refer to this problem as the
vehicle routing problem with floating targets and the main characteristic is that targets
are allowed to move from their initial home locations while waiting for a vehicle. This
problem models new applications in drone routing, ridesharing, and logistics where a
vehicle agrees to meet another vehicle or a customer at a location that is away from the
designated home location. We propose a Mixed Integer Second Order Cone Program
(MISOCP) formulation for the problem, along with valid inequalities for strengthening
the continuous relaxation. We further exploit the problem structure using a Lagrangian
decomposition and propose an exact branch-and-price algorithm. Computational results
on instances with varying characteristics are presented and the results are compared to
the solution of the full problem using CPLEX. The proposed valid inequalities reduce the
computational time of CPLEX by up to 30% on average while the proposed branch and
price is capable of solving instances where CPLEX fails in finding the optimal solution
within the imposed time limit.
History: Accepted by Karen Aardal, Area Editor for Design and Analysis of Algorithms.
Funding: Joe Naoum-Sawaya was supported by NSERC [Discovery Grant RGPIN-2017-03962] and
Bissan Ghaddar was supported by NSERC [Discovery Grant RGPIN-2017-04185].
Keywords: vehicle routing • moving targets • Lagrangian decomposition • branch and price
1. Introduction
Since the introduction of the Vehicle Routing Problem
(VRP) in Dantzig and Ramser (1959), several varia-
tions of the VRP have been addressed in the literature.
Such routing problems cover a range of practical situ-
ations and are generally challenging for decision mak-
ers mainly resulting from the difficulty in developing
efficient algorithms for finding optimal or even sub-
optimal solutions, especially when modeling real-life
applications (Toth and Vigo 2014).
The focus of this paper is to formulate and solve a
dynamic variant of VRP that we refer to as the vehi-
cle routing problem with floating targets (VRPFT). The
problem seeks to determine a set of vehicle routes
to visit a set of target points that can freely move in
the Euclidean plane. VRPFT has several applications
in practice. One such application arises in rideshar-
ing where the target points are individuals requiring a
means of transport for reaching a common destination,
such as employees of the same company (e.g., Aïvodji
et al. 2015, Bruck et al. 2015, Bit-Monnot et al. 2013
and Varone and Aissat 2015). Traditionally, a common
assumption is that vehicles will pick-up the individu-
als from their home locations that sometimes creates
undesired detours for the drivers, while in practice, the
individuals might meet the car at a more convenient
location midway on the route to the common desti-
nation (Figure 1). Another area of practical applica-
tions is related to target tracking such as missions con-
ducted by Unmanned Aerial Vehicles in military and
civilian contexts for example for surveillance, defense,
security, reconnaissance, weather monitoring, and pol-
lutant estimation (e.g., Sundar and Rathinam 2013,
Mallick et al. 2013) and aerial refueling (e.g., Barnes
et al. 2004 and Thomas et al. 2014).
Contributions of this paper. The main contributions of
this paper are (a) a mixed integer second order cone
program for the vehicle routing problem with floating
targets, (b) a branch-and-price approach to address this
problem, and (c) the derivation of valid inequalities
coupled with a computationally efficient implementa-
tion that is capable of solving problems of reasonable
size.
Outline of this paper. Following this introductory sec-
tion, Section 2 provides a literature review. The VRPFT
along with a variant that assumes that the locations
can move only in a fixed direction are formulated in
Section 3. Valid cuts for strengthening the formulations
are derived in Section 4. Section 5 presents the pro-
posed branch-and-price approach. Section 6 discusses
554
Vol. 30, No. 3, Summer 2018, pp. 554–569
http://pubsonline.informs.org/journal/ijoc/ ISSN 1091-9856 (print), ISSN 1526-5528 (online)
The Vehicle Routing Problem with Floating Targets:
Formulation and Solution Approaches
Claudio Gambella,a Joe Naoum-Sawaya,b Bissan Ghaddarb
a IBM Research, Mulhuddart, Dublin 15, Ireland; b Ivey Business School, University of Western Ontario, London, Ontario N6G 0N1, Canada
Contact: claudio.gambella@unibo.it, http://orcid.org/0000-0001-7134-0852 (CG); jnaoumsa@uwaterloo.ca,
http://orcid.org/0000-0002-4908-225X (JN-S); bghaddar@uwaterloo.ca, http://orcid.org/0000-0003-4695-200X (BG)
Received: July 13, 2016
Revised: August 15, 2017
Accepted: November 6, 2017
Published Online: October 2, 2018
https://doi.org/10.1287/ijoc.2017.0800
Copyright: © 2018 INFORMS
Abstract. This paper addresses a generalization of the vehicle routing problem in which
the pick-up locations of the targets are nonstationary. We refer to this problem as the
vehicle routing problem with floating targets and the main characteristic is that targets
are allowed to move from their initial home locations while waiting for a vehicle. This
problem models new applications in drone routing, ridesharing, and logistics where a
vehicle agrees to meet another vehicle or a customer at a location that is away from the
designated home location. We propose a Mixed Integer Second Order Cone Program
(MISOCP) formulation for the problem, along with valid inequalities for strengthening
the continuous relaxation. We further exploit the problem structure using a Lagrangian
decomposition and propose an exact branch-and-price algorithm. Computational results
on instances with varying characteristics are presented and the results are compared to
the solution of the full problem using CPLEX. The proposed valid inequalities reduce the
computational time of CPLEX by up to 30% on average while the proposed branch and
price is capable of solving instances where CPLEX fails in finding the optimal solution
within the imposed time limit.
History: Accepted by Karen Aardal, Area Editor for Design and Analysis of Algorithms.
Funding: Joe Naoum-Sawaya was supported by NSERC [Discovery Grant RGPIN-2017-03962] and
Bissan Ghaddar was supported by NSERC [Discovery Grant RGPIN-2017-04185].
Keywords: vehicle routing • moving targets • Lagrangian decomposition • branch and price
1. Introduction
Since the introduction of the Vehicle Routing Problem
(VRP) in Dantzig and Ramser (1959), several varia-
tions of the VRP have been addressed in the literature.
Such routing problems cover a range of practical situ-
ations and are generally challenging for decision mak-
ers mainly resulting from the difficulty in developing
efficient algorithms for finding optimal or even sub-
optimal solutions, especially when modeling real-life
applications (Toth and Vigo 2014).
The focus of this paper is to formulate and solve a
dynamic variant of VRP that we refer to as the vehi-
cle routing problem with floating targets (VRPFT). The
problem seeks to determine a set of vehicle routes
to visit a set of target points that can freely move in
the Euclidean plane. VRPFT has several applications
in practice. One such application arises in rideshar-
ing where the target points are individuals requiring a
means of transport for reaching a common destination,
such as employees of the same company (e.g., Aïvodji
et al. 2015, Bruck et al. 2015, Bit-Monnot et al. 2013
and Varone and Aissat 2015). Traditionally, a common
assumption is that vehicles will pick-up the individu-
als from their home locations that sometimes creates
undesired detours for the drivers, while in practice, the
individuals might meet the car at a more convenient
location midway on the route to the common desti-
nation (Figure 1). Another area of practical applica-
tions is related to target tracking such as missions con-
ducted by Unmanned Aerial Vehicles in military and
civilian contexts for example for surveillance, defense,
security, reconnaissance, weather monitoring, and pol-
lutant estimation (e.g., Sundar and Rathinam 2013,
Mallick et al. 2013) and aerial refueling (e.g., Barnes
et al. 2004 and Thomas et al. 2014).
Contributions of this paper. The main contributions of
this paper are (a) a mixed integer second order cone
program for the vehicle routing problem with floating
targets, (b) a branch-and-price approach to address this
problem, and (c) the derivation of valid inequalities
coupled with a computationally efficient implementa-
tion that is capable of solving problems of reasonable
size.
Outline of this paper. Following this introductory sec-
tion, Section 2 provides a literature review. The VRPFT
along with a variant that assumes that the locations
can move only in a fixed direction are formulated in
Section 3. Valid cuts for strengthening the formulations
are derived in Section 4. Section 5 presents the pro-
posed branch-and-price approach. Section 6 discusses
554
Gambella et al.: The Vehicle Routing Problem with Floating Targets
INFORMS Journal on Computing, 2018, vol. 30, no. 3, pp. 554–569, © 2018 INFORMS 555
Figure 1. (Color online) A Ride-Sharing System with
Floating Pick-Up Locations
the implementation details and presents the computa-
tional results. Finally, Section 7 provides a brief conclu-
sion and future research directions.
2. Literature Review
The vehicle routing problem is a generalization of the
traveling salesman problem (TSP) that has been stud-
ied extensively in the literature. The TSP requires the
determination of a minimum-cost Hamiltonian cycle
graph (Laporte 1992, Gutin and Punnen 2002). A vari-
ant of the TSP, in which the nodes of the graph are mov-
ing during the planning horizon, is typically referred
to as moving-target TSP, kinetic TSP, or nonstationary
TSP. Hammar (2002) considered the moving target TSP
where the nodes are moving at a constant speed on a
fixed line in the Euclidean plane and proved the exis-
tence of a polynomial time approximation scheme for
the problem where the targets are sharing the same
direction and speed. Helvig et al. (2003) studied sev-
eral variants of the moving-target TSP and proposed
an exact polynomial algorithm based on dynamic pro-
gramming for the case where all the locations are on
a line. In addition, the authors addressed the moving-
target TSP with resupply, in which a vehicle is required
to head back to the depot after intercepting each tar-
get, under the restriction of targets moving along lines
passing from the depot. Jiang et al. (2005) considered
the problem in which the targets are moving with a
constant speed in a straight line in a two-dimensional
space. A genetic algorithm is also proposed and com-
putational results are presented on a randomly gener-
ated test set with 10 target nodes.
VRP refers to the cases where multiple vehicles are
available. Asahiro et al. (2006) analyzed a VRP in which
multiple interceptor vehicles, robots in their case, are
moving on straight track lines and targets are traveling
at a fixed speed. Polynomial time algorithms and proof
of NP-hardness are given for problem variants where
either the number of intercepted targets or the number
of interceptor vehicles are variables to be optimized.
Choubey (2013) considered the situation in which the
moving targets are traveling at constant speed in a
given direction and proposed a genetic algorithm and
provided computational results on a random test set
with a maximum of 10 target locations. More recently,
Stieber et al. (2015) and Stieber and Fügenschuh (2016)
addressed the moving-target VRP where the targets are
moving at a fixed speed in a linear trajectory in a mul-
tidimensional space. In the former paper, the authors
used a time-extended graph and time discretization
that lead to a very large number of variables to for-
mulate the problem as a mixed integer linear program.
A heuristic is then proposed to produce solutions in
a reasonable computational time and results are pro-
vided for instances with up to 36 targets and three vehi-
cles. The latter paper showcases four approaches to
model the time aspect of the problem and provides
solutions for instances with up to eight targets and six
salesmen. Another research stream is concerned with
TSP and VRP variants with moving targets involv-
ing uncertainty. Bopardikar et al. (2010) addressed a
dynamic routing problem in which a service vehicle
aims at intercepting mobile targets where the targets
arrive on a line segment according to a Poisson pro-
cess, and upon arrival, move with a fixed speed. The
authors unified the preliminary works of Bopardikar
et al. (2009) and Smith et al. (2009b) and formulated sta-
ble service policies for the vehicle and a novel receding-
horizon policy. The work is extended in Bopardikar
et al. (2011) to address the cases of nonuniform gen-
eration density, adversarial target motion, and multi-
ple intercepting vehicles. Gradient-based optimization
algorithms determine vehicle placements and motions
that minimize a cost function based on the maneu-
vering abilities of the targets. Agharkar and Bullo
(2014) considered a problem variant in which the tar-
gets appear stochastically and uniformly distributed
on a disk and escape radially outward with a constant
speed. Three policies for an intercepting vehicle are
introduced and compared. Finally, Smith et al. (2009a)
studied a similar problem where a service vehicle seeks
to capture the dynamically arriving targets before they
reach a boundary deadline. Vehicle policies are pro-
posed to maximize the fraction of intercepted targets
within the deadline.
Besides moving targets, other extensions of VRP
have also been studied in the literature to model prac-
tical situations. For instance, time windows may be
imposed on a vehicle reaching a particular location and
several exact and heuristic solution approaches have
been proposed (Dumas et al. 1995, Mingozzi et al. 1997,
Gendreau et al. 1998). Other model variants include
conditions that require a vehicle to visit a pick-up loca-
tion before proceeding to the associated drop-off loca-
tion (Baldacci et al. 2011). Such models are often used
for passenger transportation such as the dial-a-ride
problem that deals with the routing of the vehicles
INFORMS Journal on Computing, 2018, vol. 30, no. 3, pp. 554–569, © 2018 INFORMS 555
Figure 1. (Color online) A Ride-Sharing System with
Floating Pick-Up Locations
the implementation details and presents the computa-
tional results. Finally, Section 7 provides a brief conclu-
sion and future research directions.
2. Literature Review
The vehicle routing problem is a generalization of the
traveling salesman problem (TSP) that has been stud-
ied extensively in the literature. The TSP requires the
determination of a minimum-cost Hamiltonian cycle
graph (Laporte 1992, Gutin and Punnen 2002). A vari-
ant of the TSP, in which the nodes of the graph are mov-
ing during the planning horizon, is typically referred
to as moving-target TSP, kinetic TSP, or nonstationary
TSP. Hammar (2002) considered the moving target TSP
where the nodes are moving at a constant speed on a
fixed line in the Euclidean plane and proved the exis-
tence of a polynomial time approximation scheme for
the problem where the targets are sharing the same
direction and speed. Helvig et al. (2003) studied sev-
eral variants of the moving-target TSP and proposed
an exact polynomial algorithm based on dynamic pro-
gramming for the case where all the locations are on
a line. In addition, the authors addressed the moving-
target TSP with resupply, in which a vehicle is required
to head back to the depot after intercepting each tar-
get, under the restriction of targets moving along lines
passing from the depot. Jiang et al. (2005) considered
the problem in which the targets are moving with a
constant speed in a straight line in a two-dimensional
space. A genetic algorithm is also proposed and com-
putational results are presented on a randomly gener-
ated test set with 10 target nodes.
VRP refers to the cases where multiple vehicles are
available. Asahiro et al. (2006) analyzed a VRP in which
multiple interceptor vehicles, robots in their case, are
moving on straight track lines and targets are traveling
at a fixed speed. Polynomial time algorithms and proof
of NP-hardness are given for problem variants where
either the number of intercepted targets or the number
of interceptor vehicles are variables to be optimized.
Choubey (2013) considered the situation in which the
moving targets are traveling at constant speed in a
given direction and proposed a genetic algorithm and
provided computational results on a random test set
with a maximum of 10 target locations. More recently,
Stieber et al. (2015) and Stieber and Fügenschuh (2016)
addressed the moving-target VRP where the targets are
moving at a fixed speed in a linear trajectory in a mul-
tidimensional space. In the former paper, the authors
used a time-extended graph and time discretization
that lead to a very large number of variables to for-
mulate the problem as a mixed integer linear program.
A heuristic is then proposed to produce solutions in
a reasonable computational time and results are pro-
vided for instances with up to 36 targets and three vehi-
cles. The latter paper showcases four approaches to
model the time aspect of the problem and provides
solutions for instances with up to eight targets and six
salesmen. Another research stream is concerned with
TSP and VRP variants with moving targets involv-
ing uncertainty. Bopardikar et al. (2010) addressed a
dynamic routing problem in which a service vehicle
aims at intercepting mobile targets where the targets
arrive on a line segment according to a Poisson pro-
cess, and upon arrival, move with a fixed speed. The
authors unified the preliminary works of Bopardikar
et al. (2009) and Smith et al. (2009b) and formulated sta-
ble service policies for the vehicle and a novel receding-
horizon policy. The work is extended in Bopardikar
et al. (2011) to address the cases of nonuniform gen-
eration density, adversarial target motion, and multi-
ple intercepting vehicles. Gradient-based optimization
algorithms determine vehicle placements and motions
that minimize a cost function based on the maneu-
vering abilities of the targets. Agharkar and Bullo
(2014) considered a problem variant in which the tar-
gets appear stochastically and uniformly distributed
on a disk and escape radially outward with a constant
speed. Three policies for an intercepting vehicle are
introduced and compared. Finally, Smith et al. (2009a)
studied a similar problem where a service vehicle seeks
to capture the dynamically arriving targets before they
reach a boundary deadline. Vehicle policies are pro-
posed to maximize the fraction of intercepted targets
within the deadline.
Besides moving targets, other extensions of VRP
have also been studied in the literature to model prac-
tical situations. For instance, time windows may be
imposed on a vehicle reaching a particular location and
several exact and heuristic solution approaches have
been proposed (Dumas et al. 1995, Mingozzi et al. 1997,
Gendreau et al. 1998). Other model variants include
conditions that require a vehicle to visit a pick-up loca-
tion before proceeding to the associated drop-off loca-
tion (Baldacci et al. 2011). Such models are often used
for passenger transportation such as the dial-a-ride
problem that deals with the routing of the vehicles
Gambella et al.: The Vehicle Routing Problem with Floating Targets
556 INFORMS Journal on Computing, 2018, vol. 30, no. 3, pp. 554–569, © 2018 INFORMS
and the sequencing of passenger pick-up and drop-off
(Baldacci et al. 2004, Cordeau 2006). Reyes et al. (2017)
introduced the VRP with home and roaming delivery
locations, in which the delivery points can be chosen
from a discrete set of locations given capacity and time
windows constraints with the objective of minimizing
the vehicles travel time. Tailored heuristic algorithms
outperform Gurobi especially as the size of the instance
increases. Ozbaygin et al. (2017) proposed a branch-
and-price algorithm for a set partitioning formulation
of the VRP variant of Reyes et al. (2017). The proposed
branch-and-price approach exploits the structure of
the problem and adopts a depth-first search strategy
while branching on the variables of the original formu-
lation similar to the approach discussed in this paper.
High-quality solutions are obtained for instances with
up to 120 customers.
In this paper we address the vehicle routing prob-
lem with floating targets where the vehicles can meet
the target clients at locations that may be away from
their home. Particularly, we assume that each target can
travel within a maximum speed limit to meet a vehicle.
The vehicles are also assumed to be traveling within
a maximum speed and we assume a common destina-
tion for all the targets. The VRPFT is formulated next.
3. Problem Formulation
This section presents the VRPFT problem formulation.
We first propose the general case where the targets can
move in any direction and then present a specialized
formulation for the case where the targets can move
according to a straight line.
3.1. General Case
Given a set of n targets to be picked up by a fleet of K
vehicles, each with a capacity Q and a maximum vehi-
cle speed SV , the aim of the vehicle routing problem
with floating targets is to determine the minimum cost
vehicle routes starting from the depot O and ending at
the drop-off location D where all the targets are picked
up by a vehicle at a convenient location which we refer
to as a meeting point. At time t 0, each target j has a
starting home location Hj ∈ 2, while the starting loca-
tion of all vehicles is depot O. Furthermore, each target
is allowed to move from the designated home location
at a maximum speed ST
j .
To formulate the mathematical model, the following
binary decision variables are introduced:
xk
i j
1 if target j is the i-th target visited
by vehicle k,
0 otherwise.
yk
{
1 if vehicle k is used,
0 otherwise.
The vehicles origin O is designated as target j 0 while
the destination node D for the vehicles that are used is
designated as target j n +1. The following continuous
decision variables are also introduced to determine the
meeting points between the targets and the vehicles
and the time required to reach the meeting points. The
continuous variables are
mV
ki : coordinates in 2 of the i-th meeting point for
vehicle k,
mT
j : coordinates in 2 of the pick-up point of target j,
tV
ki : time required by vehicle k to reach the i-th
meeting point from i − 1,
tT
j : time required by target j to reach the designated
meeting point.
VRPFT can then be formulated as follows:
[OP]: min
K∑
k1
Q+1∑
i1
tV
ki (1)
s.t. ‖mV
ki − mV
k, i−1 ‖
SV ≤ tV
ki
∀ i 1, . . . , Q + 1, ∀ k 1, . . . , K (2)
‖mT
j − Hj ‖
ST
j
≤ tT
j ∀ j 1, . . . , n (3)
mV
ki ≥ mT
j − CM (1 − xk
i j ) ∀ i 1, . . . , Q,
∀ j 1, . . . , n + 1, ∀ k 1, . . . , K (4)
mV
ki ≤ mT
j + CM (1 − xk
i j ) ∀ i 1, . . . , Q,
∀ j 1, . . . , n + 1, ∀ k 1, . . . , K (5)
mV
k, Q+1 yk · D + (1 − yk ) · O
∀ k 1, . . . , K (6)
i∑
i′1
tV
ki′ ≥ tT
j − CT
j (1 − xk
i j ) ∀ i 1, . . . , Q,
∀ j 1, . . . , n, ∀ k 1, . . . , K (7)
K∑
k1
Q∑
i1
xk
i, j 1 ∀ j 1, . . . , n (8)
n∑
j′1
xk
i, j′ ≥ xk
i+1, j ∀ i 1, . . . , Q − 1,
∀ j 1, . . . , n, ∀ k 1, . . . , K (9)
yk
n∑
j1
xk
1, j ∀ k 1, . . . , K (10)
n+1∑
j1
xk
i, j yk
∀ i 2, . . . , Q, ∀ k 1, . . . , K (11)
mV
k0 O ∀ k 1, . . . , K (12)
mT
n+1 D (13)
tT
j ≥ 0 ∀ j 1, . . . , n (14)
tV
ki ≥ 0
∀ i 1, . . . , Q + 1, ∀ k 1, . . . , K (15)
556 INFORMS Journal on Computing, 2018, vol. 30, no. 3, pp. 554–569, © 2018 INFORMS
and the sequencing of passenger pick-up and drop-off
(Baldacci et al. 2004, Cordeau 2006). Reyes et al. (2017)
introduced the VRP with home and roaming delivery
locations, in which the delivery points can be chosen
from a discrete set of locations given capacity and time
windows constraints with the objective of minimizing
the vehicles travel time. Tailored heuristic algorithms
outperform Gurobi especially as the size of the instance
increases. Ozbaygin et al. (2017) proposed a branch-
and-price algorithm for a set partitioning formulation
of the VRP variant of Reyes et al. (2017). The proposed
branch-and-price approach exploits the structure of
the problem and adopts a depth-first search strategy
while branching on the variables of the original formu-
lation similar to the approach discussed in this paper.
High-quality solutions are obtained for instances with
up to 120 customers.
In this paper we address the vehicle routing prob-
lem with floating targets where the vehicles can meet
the target clients at locations that may be away from
their home. Particularly, we assume that each target can
travel within a maximum speed limit to meet a vehicle.
The vehicles are also assumed to be traveling within
a maximum speed and we assume a common destina-
tion for all the targets. The VRPFT is formulated next.
3. Problem Formulation
This section presents the VRPFT problem formulation.
We first propose the general case where the targets can
move in any direction and then present a specialized
formulation for the case where the targets can move
according to a straight line.
3.1. General Case
Given a set of n targets to be picked up by a fleet of K
vehicles, each with a capacity Q and a maximum vehi-
cle speed SV , the aim of the vehicle routing problem
with floating targets is to determine the minimum cost
vehicle routes starting from the depot O and ending at
the drop-off location D where all the targets are picked
up by a vehicle at a convenient location which we refer
to as a meeting point. At time t 0, each target j has a
starting home location Hj ∈ 2, while the starting loca-
tion of all vehicles is depot O. Furthermore, each target
is allowed to move from the designated home location
at a maximum speed ST
j .
To formulate the mathematical model, the following
binary decision variables are introduced:
xk
i j
1 if target j is the i-th target visited
by vehicle k,
0 otherwise.
yk
{
1 if vehicle k is used,
0 otherwise.
The vehicles origin O is designated as target j 0 while
the destination node D for the vehicles that are used is
designated as target j n +1. The following continuous
decision variables are also introduced to determine the
meeting points between the targets and the vehicles
and the time required to reach the meeting points. The
continuous variables are
mV
ki : coordinates in 2 of the i-th meeting point for
vehicle k,
mT
j : coordinates in 2 of the pick-up point of target j,
tV
ki : time required by vehicle k to reach the i-th
meeting point from i − 1,
tT
j : time required by target j to reach the designated
meeting point.
VRPFT can then be formulated as follows:
[OP]: min
K∑
k1
Q+1∑
i1
tV
ki (1)
s.t. ‖mV
ki − mV
k, i−1 ‖
SV ≤ tV
ki
∀ i 1, . . . , Q + 1, ∀ k 1, . . . , K (2)
‖mT
j − Hj ‖
ST
j
≤ tT
j ∀ j 1, . . . , n (3)
mV
ki ≥ mT
j − CM (1 − xk
i j ) ∀ i 1, . . . , Q,
∀ j 1, . . . , n + 1, ∀ k 1, . . . , K (4)
mV
ki ≤ mT
j + CM (1 − xk
i j ) ∀ i 1, . . . , Q,
∀ j 1, . . . , n + 1, ∀ k 1, . . . , K (5)
mV
k, Q+1 yk · D + (1 − yk ) · O
∀ k 1, . . . , K (6)
i∑
i′1
tV
ki′ ≥ tT
j − CT
j (1 − xk
i j ) ∀ i 1, . . . , Q,
∀ j 1, . . . , n, ∀ k 1, . . . , K (7)
K∑
k1
Q∑
i1
xk
i, j 1 ∀ j 1, . . . , n (8)
n∑
j′1
xk
i, j′ ≥ xk
i+1, j ∀ i 1, . . . , Q − 1,
∀ j 1, . . . , n, ∀ k 1, . . . , K (9)
yk
n∑
j1
xk
1, j ∀ k 1, . . . , K (10)
n+1∑
j1
xk
i, j yk
∀ i 2, . . . , Q, ∀ k 1, . . . , K (11)
mV
k0 O ∀ k 1, . . . , K (12)
mT
n+1 D (13)
tT
j ≥ 0 ∀ j 1, . . . , n (14)
tV
ki ≥ 0
∀ i 1, . . . , Q + 1, ∀ k 1, . . . , K (15)
Gambella et al.: The Vehicle Routing Problem with Floating Targets
INFORMS Journal on Computing, 2018, vol. 30, no. 3, pp. 554–569, © 2018 INFORMS 557
xk
i, j ∈ {0, 1}
∀ i 1, . . . , Q, ∀ j 1, . . . , n + 1,
∀ k 1, . . . , K, (i, j) , (1, n + 1) (16)
yk ∈ {0, 1} ∀ k 1, . . . , K. (17)
The objective function (1) minimizes the total travel
time of the vehicles. Constraints (2) ensure that the
total travel time for a vehicle between two consecutive
locations is no less than the travel time that is required
given a maximum speed SV . We note that the distances
are computed via the Euclidean norm ‖ · ‖ (‖ · ‖ : ‖ · ‖2).
Constraints (3) ensure that the travel time for each tar-
get between the home location and the pick-up location
is no less than the travel time that is required given
a maximum speed ST
j . It can be observed that con-
straints (3) allow each target to remain at the home
location, in the case where it coincides with the pick-up
location. Constraints (4) and (5) indicate that if target j
is the i-th target to be visited by vehicle k then vehicle k
and target j should meet at the same location mT
j mV
ki .
Hence constraints (4) and (5) enforce the following log-
ical conditions using the “big-M” coefficient CM :
mT
j mV
ki if xk
i j 1 ∀ i 1, . . . , Q,
∀ k 1, . . . , K, ∀ j 1, . . . , n + 1.
The constant CM (CM
x , CM
y ) in (4) and (5) can be safely
defined as CM
x Xmax − Xmin, CM
y Ymax − Ymin, where
Xmax, Xmin, Ymax, Ymin are limits on the meeting point
locations. Constraints (6) indicate that if a vehicle is
used then it should end the tour at the drop-off loca-
tion D otherwise the vehicle remains at the depot O.
Constraints (7) impose the synchronization between
the vehicles and targets by not allowing a vehicle to
depart before the arrival of the target through enforc-
ing the following logical conditions using the “big-M”
coefficients CT
j :
i∑
i′1
tV
ki′ ≥ tT
j if xk
i, j 1 ∀ i 1, . . . , Q,
∀ k 1, . . . , K, ∀ j 1, . . . , n.
The constant CT
j in (7) can be safely defined as CT
j
√(Xmax − Xmin)2 − (Ymax − Ymin)2/ST
j + ¯wj where ¯wj is
the maximum allowable waiting time for target j.
The requirement that each target is picked up by
exactly one vehicle is expressed in constraints (8). Con-
straints (9) impose the order of the targets that are inter-
cepted by each vehicle and that n + 1 is the last target
visited by a used vehicle. We note that these constraints
are a stronger version of the valid constraints:
n∑
j1
xk
i, j ≥
n∑
j1
xk
i+1, j ∀ i 1, . . . , Q − 1, ∀ k 1, . . . , K.
Constraints (10) follow from the definition of the y vari-
ables while constraints (11) are necessary to express
that a vehicle that left the depot should proceed to
pick up a target. Constraints (12) state that each vehi-
cle is at the depot O at time t 0 while constraint (13)
indicate that D is the final destination of each route.
Finally, constraints (14)–(17) define the decision vari-
ables of the problem. We note that variables xk
1, n+1 are
not defined in the model since no vehicle will leave the
depot directly to the drop-off location. Furthermore,
the definition of the x variables in terms of the pick-up
sequence has the advantage of naturally enforcing the
maximum capacity Q on the fleet of vehicle by only
using the variables xk
i, j with i ≤ Q.
Model (1)–(17) is a Mixed-Integer Second Order
Cone Program (MISOCP). It consists of a linear objec-
tive function, linear constraints, and second order cone
constraints ((2) and (3)). To solve the model with an
optimization solver such as CPLEX, it is generally
required to rewrite the second order cone constraints
in the standard quadratic form
‖x‖ ≤ t x ∈ n , t ∈ .
For that, the auxiliary variables ηV
ki , τV
ki , ηT
j , and τT
j are
introduced and constraints (2) and (3) are replaced by
ηV
ki mV
ki − mV
k, i−1 , ∀ i 1, . . . , Q + 1, ∀ k 1, . . . , K;
τV
ki SV tV
ki , ∀ i 1, . . . , Q + 1, ∀ k 1, . . . , K;
ηT
j mT
j − Hj , ∀ j 1, . . . , n;
τT
j ST
j tT
j , ∀ j 1, . . . , n;
‖ηV
ki ‖ ≤ τV
ki , ∀ i 1, . . . , Q + 1, ∀ k 1, . . . , K;
‖ηT
j ‖ ≤ τT
j , ∀ j 1, . . . , n.
Model (1)–(17) assumes the general VRPFT where
the targets can meet the vehicle in any location that
falls within the bounds Xmax, Xmin, Ymax, and Ymin. Sec-
tion 3.2 presents the particular case where the targets
are only allowed to move in a predefined direction.
3.2. Targets Moving Along a Fixed Line
For the special case where the targets can only move
according to a straight line, model (1)–(17) can be mod-
ified to include constraints to limit the trajectories of
the targets. Particularly, the assumption is that each
target j can move according to a direction vector dj
and a scalar λj parametrizes the travel trajectory. The
limitations in determining the meeting points are then
imposed using the following equations:
mT
j − Hj λj dj , ∀ j 1, . . . , n, (18)
and constraints (3) reduce to the linear conditions
‖dj ‖λj
ST
j
≤ tT
j , ∀ j 1, . . . , n. (19)
INFORMS Journal on Computing, 2018, vol. 30, no. 3, pp. 554–569, © 2018 INFORMS 557
xk
i, j ∈ {0, 1}
∀ i 1, . . . , Q, ∀ j 1, . . . , n + 1,
∀ k 1, . . . , K, (i, j) , (1, n + 1) (16)
yk ∈ {0, 1} ∀ k 1, . . . , K. (17)
The objective function (1) minimizes the total travel
time of the vehicles. Constraints (2) ensure that the
total travel time for a vehicle between two consecutive
locations is no less than the travel time that is required
given a maximum speed SV . We note that the distances
are computed via the Euclidean norm ‖ · ‖ (‖ · ‖ : ‖ · ‖2).
Constraints (3) ensure that the travel time for each tar-
get between the home location and the pick-up location
is no less than the travel time that is required given
a maximum speed ST
j . It can be observed that con-
straints (3) allow each target to remain at the home
location, in the case where it coincides with the pick-up
location. Constraints (4) and (5) indicate that if target j
is the i-th target to be visited by vehicle k then vehicle k
and target j should meet at the same location mT
j mV
ki .
Hence constraints (4) and (5) enforce the following log-
ical conditions using the “big-M” coefficient CM :
mT
j mV
ki if xk
i j 1 ∀ i 1, . . . , Q,
∀ k 1, . . . , K, ∀ j 1, . . . , n + 1.
The constant CM (CM
x , CM
y ) in (4) and (5) can be safely
defined as CM
x Xmax − Xmin, CM
y Ymax − Ymin, where
Xmax, Xmin, Ymax, Ymin are limits on the meeting point
locations. Constraints (6) indicate that if a vehicle is
used then it should end the tour at the drop-off loca-
tion D otherwise the vehicle remains at the depot O.
Constraints (7) impose the synchronization between
the vehicles and targets by not allowing a vehicle to
depart before the arrival of the target through enforc-
ing the following logical conditions using the “big-M”
coefficients CT
j :
i∑
i′1
tV
ki′ ≥ tT
j if xk
i, j 1 ∀ i 1, . . . , Q,
∀ k 1, . . . , K, ∀ j 1, . . . , n.
The constant CT
j in (7) can be safely defined as CT
j
√(Xmax − Xmin)2 − (Ymax − Ymin)2/ST
j + ¯wj where ¯wj is
the maximum allowable waiting time for target j.
The requirement that each target is picked up by
exactly one vehicle is expressed in constraints (8). Con-
straints (9) impose the order of the targets that are inter-
cepted by each vehicle and that n + 1 is the last target
visited by a used vehicle. We note that these constraints
are a stronger version of the valid constraints:
n∑
j1
xk
i, j ≥
n∑
j1
xk
i+1, j ∀ i 1, . . . , Q − 1, ∀ k 1, . . . , K.
Constraints (10) follow from the definition of the y vari-
ables while constraints (11) are necessary to express
that a vehicle that left the depot should proceed to
pick up a target. Constraints (12) state that each vehi-
cle is at the depot O at time t 0 while constraint (13)
indicate that D is the final destination of each route.
Finally, constraints (14)–(17) define the decision vari-
ables of the problem. We note that variables xk
1, n+1 are
not defined in the model since no vehicle will leave the
depot directly to the drop-off location. Furthermore,
the definition of the x variables in terms of the pick-up
sequence has the advantage of naturally enforcing the
maximum capacity Q on the fleet of vehicle by only
using the variables xk
i, j with i ≤ Q.
Model (1)–(17) is a Mixed-Integer Second Order
Cone Program (MISOCP). It consists of a linear objec-
tive function, linear constraints, and second order cone
constraints ((2) and (3)). To solve the model with an
optimization solver such as CPLEX, it is generally
required to rewrite the second order cone constraints
in the standard quadratic form
‖x‖ ≤ t x ∈ n , t ∈ .
For that, the auxiliary variables ηV
ki , τV
ki , ηT
j , and τT
j are
introduced and constraints (2) and (3) are replaced by
ηV
ki mV
ki − mV
k, i−1 , ∀ i 1, . . . , Q + 1, ∀ k 1, . . . , K;
τV
ki SV tV
ki , ∀ i 1, . . . , Q + 1, ∀ k 1, . . . , K;
ηT
j mT
j − Hj , ∀ j 1, . . . , n;
τT
j ST
j tT
j , ∀ j 1, . . . , n;
‖ηV
ki ‖ ≤ τV
ki , ∀ i 1, . . . , Q + 1, ∀ k 1, . . . , K;
‖ηT
j ‖ ≤ τT
j , ∀ j 1, . . . , n.
Model (1)–(17) assumes the general VRPFT where
the targets can meet the vehicle in any location that
falls within the bounds Xmax, Xmin, Ymax, and Ymin. Sec-
tion 3.2 presents the particular case where the targets
are only allowed to move in a predefined direction.
3.2. Targets Moving Along a Fixed Line
For the special case where the targets can only move
according to a straight line, model (1)–(17) can be mod-
ified to include constraints to limit the trajectories of
the targets. Particularly, the assumption is that each
target j can move according to a direction vector dj
and a scalar λj parametrizes the travel trajectory. The
limitations in determining the meeting points are then
imposed using the following equations:
mT
j − Hj λj dj , ∀ j 1, . . . , n, (18)
and constraints (3) reduce to the linear conditions
‖dj ‖λj
ST
j
≤ tT
j , ∀ j 1, . . . , n. (19)
Gambella et al.: The Vehicle Routing Problem with Floating Targets
558 INFORMS Journal on Computing, 2018, vol. 30, no. 3, pp. 554–569, © 2018 INFORMS
VRPFT with fixed line moving directions is then for-
mulated as
min (1)
s.t (2), (4)–(17);
(18), (19);
λj ≥ 0, ∀ j 1, . . . , n,
where the conic constraints (3) in the general VRPFT
are replaced by the linear constraints (18) and (19).
Since the resulting model contains less conic con-
straints, the VRPFT with fixed line moving directions is
computationally easier to solve than the general VRPFT
as demonstrated in the computational results section.
Finally we note that the proposed models make the
assumption that the targets and the vehicles can travel
freely in the Euclidean plane and are allowed to wait
at the meeting points. Potentially constraints that limit
such assumptions might be needed to limit the free
travel of targets and vehicles to accommodate the speci-
ficities of the particular applications.
4. Valid Cuts
In this section, we propose a set of valid cuts for the
VRPFT. These cuts are valid for model (1)–(17) but can
strengthen the continuous relaxation and consequently
speed up the solution of the problem.
4.1. Final Destination
In model (1)–(17), the final destination D for the vehi-
cle routes is enforced using constraints (9) and (11).
This condition can be also enforced using the following
constraints:
xk
i, n+1 ≤ xk
i+1, n+1 , ∀ i 2, . . . , Q − 1, ∀ k 1, . . . K, (20)
which indicate that if the i-th target for vehicle k is the
destination node, then that vehicle will remain at the
destination node by forcing all subsequent locations
for vehicle k to be n + 1. Furthermore the constraints
Q∑
i′i+1
n∑
j1
xk
i′ , j + (Q − i)xk
i, n+1 ≤ (Q − i)yk ,
∀ i 2, . . . , Q − 1, ∀ k 1, . . . K (21)
are also valid and indicate that if the i-th target for
vehicle k is the destination node, then the vehicle will
not serve any other target.
Theorem 1. Constraints (21) are valid for VRPFT.
Proof. From constraints (11), we have that the follow-
ing equalities hold ∀ i 2, . . . , Q − 1, ∀ k 1, . . . K:
Q∑
i′i+1
n∑
j1
xk
i′ , j
Q∑
i′i+1
(yk − xk
i′ , n+1) (Q − i)yk −
Q∑
i′i+1
xk
i′ , n+1.
From (20) it follows that
(Q − i)xk
i, n+1 ≤
Q∑
i′i+1
xk
i′ , n+1 , ∀ i 2, . . . , Q −1, ∀ k 1, . . . K,
hence (21) are valid.
4.2. Homogeneous Fleet
Taking advantage of the assumption of identical vehi-
cles, valid inequalities can be added to model (1)–(17).
Particularly, the following constraints are valid:
y1 1, (22)
yk+1 ≤ yk , ∀ k 1, . . . , K − 1. (23)
Since at least one vehicle must be used, then con-
straint (22) forces vehicle 1 to be used without loss
of generality while constraints (23) indicate that each
vehicle k cannot be used unless vehicles 1, . . . , k − 1 are
used as well.
4.3. Vehicles Order
In addition to constraints (22)–(23), we propose fami-
lies of cuts inspired by the conditions that are described
in Fischetti et al. (1995) and used in Coelho and Laporte
(2013). These cuts arise from the fact that given a fea-
sible solution of VRPFT, it is always possible to con-
struct an equivalent solution in which each vehicle k is
allowed to pick-up target j only if vehicle k − 1 picks up
a target with an index that is smaller than j and thus
the following cuts are valid:
Q−1∑
i1
xk
i, j ≤
Q−1∑
i′1
j′< j∑
j′1
xk−1
i′ , j′ ,
∀ j 2, . . . , n, ∀ k 2, . . . , K. (24)
Theorem 2. Constraints (24) are valid for VRPFT.
Proof. Consider a feasible solution for VRPFT that also
satisfies (22)–(23). Since the vehicles are identical, then
there exists a permutation σ on the set of vehicles
{1, . . . , K} such that
t(σ(1)) ≤ · · · ≤ t(σ(K)),
where t(k):min{ j ∈ {1,..., n} | ∃ i ∈ {1,..., n}: xk
i j 1} for
k ∈ {1,...,K}. Without loss of generality, we can reorder
the vehicles according to permutation σ such that
t(1) ≤ · · · ≤ t(K)
and constraints (24) are therefore valid.
558 INFORMS Journal on Computing, 2018, vol. 30, no. 3, pp. 554–569, © 2018 INFORMS
VRPFT with fixed line moving directions is then for-
mulated as
min (1)
s.t (2), (4)–(17);
(18), (19);
λj ≥ 0, ∀ j 1, . . . , n,
where the conic constraints (3) in the general VRPFT
are replaced by the linear constraints (18) and (19).
Since the resulting model contains less conic con-
straints, the VRPFT with fixed line moving directions is
computationally easier to solve than the general VRPFT
as demonstrated in the computational results section.
Finally we note that the proposed models make the
assumption that the targets and the vehicles can travel
freely in the Euclidean plane and are allowed to wait
at the meeting points. Potentially constraints that limit
such assumptions might be needed to limit the free
travel of targets and vehicles to accommodate the speci-
ficities of the particular applications.
4. Valid Cuts
In this section, we propose a set of valid cuts for the
VRPFT. These cuts are valid for model (1)–(17) but can
strengthen the continuous relaxation and consequently
speed up the solution of the problem.
4.1. Final Destination
In model (1)–(17), the final destination D for the vehi-
cle routes is enforced using constraints (9) and (11).
This condition can be also enforced using the following
constraints:
xk
i, n+1 ≤ xk
i+1, n+1 , ∀ i 2, . . . , Q − 1, ∀ k 1, . . . K, (20)
which indicate that if the i-th target for vehicle k is the
destination node, then that vehicle will remain at the
destination node by forcing all subsequent locations
for vehicle k to be n + 1. Furthermore the constraints
Q∑
i′i+1
n∑
j1
xk
i′ , j + (Q − i)xk
i, n+1 ≤ (Q − i)yk ,
∀ i 2, . . . , Q − 1, ∀ k 1, . . . K (21)
are also valid and indicate that if the i-th target for
vehicle k is the destination node, then the vehicle will
not serve any other target.
Theorem 1. Constraints (21) are valid for VRPFT.
Proof. From constraints (11), we have that the follow-
ing equalities hold ∀ i 2, . . . , Q − 1, ∀ k 1, . . . K:
Q∑
i′i+1
n∑
j1
xk
i′ , j
Q∑
i′i+1
(yk − xk
i′ , n+1) (Q − i)yk −
Q∑
i′i+1
xk
i′ , n+1.
From (20) it follows that
(Q − i)xk
i, n+1 ≤
Q∑
i′i+1
xk
i′ , n+1 , ∀ i 2, . . . , Q −1, ∀ k 1, . . . K,
hence (21) are valid.
4.2. Homogeneous Fleet
Taking advantage of the assumption of identical vehi-
cles, valid inequalities can be added to model (1)–(17).
Particularly, the following constraints are valid:
y1 1, (22)
yk+1 ≤ yk , ∀ k 1, . . . , K − 1. (23)
Since at least one vehicle must be used, then con-
straint (22) forces vehicle 1 to be used without loss
of generality while constraints (23) indicate that each
vehicle k cannot be used unless vehicles 1, . . . , k − 1 are
used as well.
4.3. Vehicles Order
In addition to constraints (22)–(23), we propose fami-
lies of cuts inspired by the conditions that are described
in Fischetti et al. (1995) and used in Coelho and Laporte
(2013). These cuts arise from the fact that given a fea-
sible solution of VRPFT, it is always possible to con-
struct an equivalent solution in which each vehicle k is
allowed to pick-up target j only if vehicle k − 1 picks up
a target with an index that is smaller than j and thus
the following cuts are valid:
Q−1∑
i1
xk
i, j ≤
Q−1∑
i′1
j′< j∑
j′1
xk−1
i′ , j′ ,
∀ j 2, . . . , n, ∀ k 2, . . . , K. (24)
Theorem 2. Constraints (24) are valid for VRPFT.
Proof. Consider a feasible solution for VRPFT that also
satisfies (22)–(23). Since the vehicles are identical, then
there exists a permutation σ on the set of vehicles
{1, . . . , K} such that
t(σ(1)) ≤ · · · ≤ t(σ(K)),
where t(k):min{ j ∈ {1,..., n} | ∃ i ∈ {1,..., n}: xk
i j 1} for
k ∈ {1,...,K}. Without loss of generality, we can reorder
the vehicles according to permutation σ such that
t(1) ≤ · · · ≤ t(K)
and constraints (24) are therefore valid.
Gambella et al.: The Vehicle Routing Problem with Floating Targets
INFORMS Journal on Computing, 2018, vol. 30, no. 3, pp. 554–569, © 2018 INFORMS 559
4.4. Unserved Targets
Valid cuts can also be derived based on the number of
targets not served by any vehicle with index not greater
than k that is given by
Lk n −
(
Q −
Q∑
i2
x1
i, n+1
)
︸ ︷︷ ︸
targets not served by vehicle 1
−
k∑
k′2
(
Q yk′ −
Q∑
i2
xk′
i, n+1
)
︸ ︷︷ ︸
targets served by vehicle k′
,
∀ k 1, . . . , K − 1.
Particularly, the following cuts are valid:
n −
(
Q −
Q∑
i2
x1
i, n+1
)
−
k∑
k′2
(
Q yk′ −
Q∑
i2
xk′
i, n+1
)
≤ (n − k)yk+1 , ∀ k 1, . . . , K − 1, (25)
n −
(
Q −
Q∑
i2
x1
i, n+1
)
−
k∑
k′2
(
Q yk′ −
Q∑
i2
xk′
i, n+1
)
≥ yk+1 ,
∀ k 1, . . . , K − 1. (26)
Theorem 3. Constraints (25)–(26) are valid for VRPFT.
Proof. Lk varies between 0 and n − k. If Lk is strictly
greater than 0 then k vehicles are not sufficient for serv-
ing all targets and therefore vehicle k + 1 has to be
used which can be imposed by setting Lk ≤ (n − k)yk+1
∀ k 1, . . . , K − 1 and thus (25) are valid. Otherwise, if
Lk 0 then all targets can be picked up by the first k
vehicles and hence vehicle k + 1 is not needed. This can
be imposed by setting Lk ≥ yk+1 ∀ k 1, . . . , K − 1 and
thus (26) are valid.
As discussed in Section 6.5, the addition of the
proposed valid cuts reduces the computational time
for solving VRPFT. However, the problem remains
challenging to solve. The following section presents
a branch-and-price approach that exploits the struc-
ture of the problem to achieve a better computational
performance.
5. Branch-and-Price
In this section, we describe the different components of
the branch-and-price solution approach. An analogous
branch-and-price approach is adopted in Elhedhli et al.
(2011) on a bin-packing problem variant. We start first
by applying a Lagrangian relaxation to [OP].
5.1. Lagrangian Relaxation
Lagrangian relaxation is a well-known algorithm that
has been used as a solution approach for several com-
plex optimization problems (Fisher 2004, Frangioni
2005). Particularly, Lagrangian relaxation has been
used to address various variants of the vehicle routing
problem (Desrochers et al. 1992, Fisher et al. 1997, Kohl
and Madsen 1997). The common approach is to relax
the assignment constraints of targets to vehicles. For
VRPFT, the Lagrangian relaxation is applied to con-
straints (8) using multipliers µj to obtain the following
subproblem:
[SP]: vSP(µ) min
{ K∑
k1
Q+1∑
i1
tV
ki −
K∑
k1
Q∑
i1
n∑
j1
µj xk
i, j +
[ n∑
j1
µj
] }
s.t (2)–(7), (9)–(17).
Problem [SP] is decomposable into K identical single
vehicle subproblems
[SSP]:
vSSP(µ) min
{Q+1∑
i1
tV
i −
n∑
j1
Q∑
i1
µj xi, j
}
(27)
s.t ‖mV
i − mV
i−1 ‖
SV ≤ tV
i , ∀ i 1, . . . , Q +1; (28)
‖mT
j − Hj ‖
ST
j
≤ tT
j , ∀ j 1, . . . , n; (29)
mV
i ≥ mT
j − CM (1− xi j ),
∀ i 1, . . . , Q, ∀ j 1, . . . , n +1; (30)
mV
i ≤ mT
j + CM (1− xi j ),
∀ i 1, . . . , Q, ∀ j 1, . . . , n +1; (31)
mV
Q+1 y · D +(1− y)· O; (32)
i∑
i′1
tV
i′ ≥ tT
j − CT (1− xi j ),
∀ i 1, . . . , Q, ∀ j 1, . . . , n′; (33)
n∑
j′1
xi, j′ ≥ xi+1, j ,
∀ j 1, . . . , n, ∀ i 1, . . . , Q −1; (34)
y
n∑
j1
x1, j ; (35)
n+1∑
j1
xi, j y, ∀ i 2, . . . , Q; (36)
mV
0 O; (37)
mT
n+1 D; (38)
tT
j ≥ 0, ∀ j 1, . . . , n; (39)
tV
i ≥ 0, ∀ i 1, . . . , Q +1; (40)
xi, j ∈ {0, 1}, ∀ i 1, . . . , Q,
∀ j 1, . . . , n +1, (i, j),(1, n +1); (41)
y ∈ {0, 1}. (42)
Note that if the fixed line moving direction case of
VRPFT is assumed, then in that case, constraints (29)
are replaced by constraints (18) and (19).
The value of the Lagrangian bound vLR(µ) is
v(LR(µ)) K · v(SSP(µ)) +
n∑
j1
µj ,
INFORMS Journal on Computing, 2018, vol. 30, no. 3, pp. 554–569, © 2018 INFORMS 559
4.4. Unserved Targets
Valid cuts can also be derived based on the number of
targets not served by any vehicle with index not greater
than k that is given by
Lk n −
(
Q −
Q∑
i2
x1
i, n+1
)
︸ ︷︷ ︸
targets not served by vehicle 1
−
k∑
k′2
(
Q yk′ −
Q∑
i2
xk′
i, n+1
)
︸ ︷︷ ︸
targets served by vehicle k′
,
∀ k 1, . . . , K − 1.
Particularly, the following cuts are valid:
n −
(
Q −
Q∑
i2
x1
i, n+1
)
−
k∑
k′2
(
Q yk′ −
Q∑
i2
xk′
i, n+1
)
≤ (n − k)yk+1 , ∀ k 1, . . . , K − 1, (25)
n −
(
Q −
Q∑
i2
x1
i, n+1
)
−
k∑
k′2
(
Q yk′ −
Q∑
i2
xk′
i, n+1
)
≥ yk+1 ,
∀ k 1, . . . , K − 1. (26)
Theorem 3. Constraints (25)–(26) are valid for VRPFT.
Proof. Lk varies between 0 and n − k. If Lk is strictly
greater than 0 then k vehicles are not sufficient for serv-
ing all targets and therefore vehicle k + 1 has to be
used which can be imposed by setting Lk ≤ (n − k)yk+1
∀ k 1, . . . , K − 1 and thus (25) are valid. Otherwise, if
Lk 0 then all targets can be picked up by the first k
vehicles and hence vehicle k + 1 is not needed. This can
be imposed by setting Lk ≥ yk+1 ∀ k 1, . . . , K − 1 and
thus (26) are valid.
As discussed in Section 6.5, the addition of the
proposed valid cuts reduces the computational time
for solving VRPFT. However, the problem remains
challenging to solve. The following section presents
a branch-and-price approach that exploits the struc-
ture of the problem to achieve a better computational
performance.
5. Branch-and-Price
In this section, we describe the different components of
the branch-and-price solution approach. An analogous
branch-and-price approach is adopted in Elhedhli et al.
(2011) on a bin-packing problem variant. We start first
by applying a Lagrangian relaxation to [OP].
5.1. Lagrangian Relaxation
Lagrangian relaxation is a well-known algorithm that
has been used as a solution approach for several com-
plex optimization problems (Fisher 2004, Frangioni
2005). Particularly, Lagrangian relaxation has been
used to address various variants of the vehicle routing
problem (Desrochers et al. 1992, Fisher et al. 1997, Kohl
and Madsen 1997). The common approach is to relax
the assignment constraints of targets to vehicles. For
VRPFT, the Lagrangian relaxation is applied to con-
straints (8) using multipliers µj to obtain the following
subproblem:
[SP]: vSP(µ) min
{ K∑
k1
Q+1∑
i1
tV
ki −
K∑
k1
Q∑
i1
n∑
j1
µj xk
i, j +
[ n∑
j1
µj
] }
s.t (2)–(7), (9)–(17).
Problem [SP] is decomposable into K identical single
vehicle subproblems
[SSP]:
vSSP(µ) min
{Q+1∑
i1
tV
i −
n∑
j1
Q∑
i1
µj xi, j
}
(27)
s.t ‖mV
i − mV
i−1 ‖
SV ≤ tV
i , ∀ i 1, . . . , Q +1; (28)
‖mT
j − Hj ‖
ST
j
≤ tT
j , ∀ j 1, . . . , n; (29)
mV
i ≥ mT
j − CM (1− xi j ),
∀ i 1, . . . , Q, ∀ j 1, . . . , n +1; (30)
mV
i ≤ mT
j + CM (1− xi j ),
∀ i 1, . . . , Q, ∀ j 1, . . . , n +1; (31)
mV
Q+1 y · D +(1− y)· O; (32)
i∑
i′1
tV
i′ ≥ tT
j − CT (1− xi j ),
∀ i 1, . . . , Q, ∀ j 1, . . . , n′; (33)
n∑
j′1
xi, j′ ≥ xi+1, j ,
∀ j 1, . . . , n, ∀ i 1, . . . , Q −1; (34)
y
n∑
j1
x1, j ; (35)
n+1∑
j1
xi, j y, ∀ i 2, . . . , Q; (36)
mV
0 O; (37)
mT
n+1 D; (38)
tT
j ≥ 0, ∀ j 1, . . . , n; (39)
tV
i ≥ 0, ∀ i 1, . . . , Q +1; (40)
xi, j ∈ {0, 1}, ∀ i 1, . . . , Q,
∀ j 1, . . . , n +1, (i, j),(1, n +1); (41)
y ∈ {0, 1}. (42)
Note that if the fixed line moving direction case of
VRPFT is assumed, then in that case, constraints (29)
are replaced by constraints (18) and (19).
The value of the Lagrangian bound vLR(µ) is
v(LR(µ)) K · v(SSP(µ)) +
n∑
j1
µj ,
Gambella et al.: The Vehicle Routing Problem with Floating Targets
560 INFORMS Journal on Computing, 2018, vol. 30, no. 3, pp. 554–569, © 2018 INFORMS
and the best Lagrangian bound is given by vLR
maxµ∈n vLR(µ). Given H, the set of feasible solutions
of [SSP], the best Lagrangian bound can be found
by solving
max
µ
{
K · min
h1,...,H
{Q+1∑
i1
tV
i, (h) −
n∑
j1
Q∑
i1
µj xi, j, (h)
}
+
n∑
j1
µj
}
,
which is equivalent to the Lagrangian master problem:
[LMP]: max
{ n∑
j1
µj + Kθ
}
(43)
s.t
n∑
j1
Q∑
i1
µj xi, j, (h) + θ ≤
Q+1∑
i1
tV
i, (h) , ∀ h ∈ H.
(44)
Denoting with αh the dual variables associated with
constraints (44), the dual of [LMP] is the Dantzig-Wolfe
master problem:
[DMP]: min ∑
h∈H
αh
Q+1∑
i1
tV
i, (h)
s.t. ∑
h∈H
αh K;
∑
h∈H
αh
Q∑
i1
xi, j, (h) 1, ∀ j 1, . . . , n;
αh ≥ 0, ∀ h ∈ H.
Since the set H is not known beforehand, the La-
grangian bound vLR is calculated iteratively where
a relaxed version of [LMP] is solved to obtain the
Lagrange multipliers µj and then [SSP] is solved lead-
ing to a new cut in [LMP]. Note that a new cut in [LMP]
is equivalent to a new column in [DMP]. Solving the
relaxed version of [LMP] provides an upper bound on
the optimal Lagrangian bound vLR while the optimal
solution of [SSP] provides a lower bound vLR(µ). The iter-
ative approach is stopped when the upper and lower
bounds are equivalent. Being a relaxed problem, the
optimal solution of [DMP] or equivalently [LMP] pro-
vides a lower bound on the optimal solution of [OP].
5.2. Tightening the Lagrangian Bound
A main advantage for the application of the presented
Lagrangian relaxation is the decomposition of the
problem into [SSP] that is computationally less chal-
lenging to solve than [OP]. However, because of the
relaxation, the resulting Lagrangian bound is a lower
bound to [OP]. The Lagrangian bound can be tight-
ened by the addition of constraints that are redundant
to [OP] but cut a part of the feasible solutions of [SSP].
Particularly the inequalities
Q∑
i1
xi, j ≤ 1, ∀ j 1, . . . , n (45)
are valid to [OP] and improve the Lagrangian bound
when added to [SSP]. Constraints (45) indicate that each
target j should be visited by a vehicle at most once.
The Lagrangian bounds are used in a branch-
and-bound framework to obtain an optimal solution
to [OP]. As discussed next, constraints that main-
tain the decomposable structure of [SP] are used for
branching.
5.3. Branching Strategy
At each node of the branch-and-bound tree, the col-
umns matrix corresponding to [DMP] is
X
∑Q
i1 xi, 1, 1
∑Q
i1 xi, 1, 2 . . . ∑Q
i1 xi, 1, |H|
∑Q
i1 xi, 2, 1
∑Q
i1 xi, 2, 2 . . . ∑Q
i1 xi, 2, |H |
. . . . . . . . . . . .
∑Q
i1 xi, n, 1
∑Q
i1 xi, n, 2 . . . ∑Q
i1 xi, n, |H|
,
where each column h is associated with a value ¯αh that
is given by the optimal solution of [DMP] at that node.
Branching is needed when two columns h1 and h2
are associated with a fractional αh and contain the
pattern
. . . h1 . . . h2 . . .
. . . . . . . . . . . . . . . . . .
j1 . . . 1 . . . 1 . . .
. . . . . . . . . . . . . . . . . .
j2 . . . 1 . . . 0 . . .
. . . . . . . . . . . . . . . . . .
in the columns matrix X. Alternatively, when such a
pattern with fractional αh does not exist, the optimal
solution of [DMP] satisfies the integrality conditions
and a feasible solution to [OP] is found. Being a min-
imization problem, this feasible solution provides an
upper bound to [OP] and the incumbent which denotes
the best upper bound is updated. A node is fathomed
if the objective function value of [DMP] at that node
is not lower than the incumbent. As discussed in Sec-
tion 5.1, since vLR(µ) provides a lower bound, then a
node is fathomed when vLR(µ) is not lower than the
incumbent. When all the nodes in the tree are fath-
omed, the resulting incumbent is an optimal solution
to [OP].
When branching, the challenge is in devising branch-
ing constraints that can maintain the decomposable
structure of the subproblem when added. We thus pro-
pose branching constraints inspired from the Ryan-
Foster branching rules (Ryan and Foster 1981) that
have been successfully used in branch-and-price algo-
rithms with separable subproblems (Mehrotra and
Trick 1996).
560 INFORMS Journal on Computing, 2018, vol. 30, no. 3, pp. 554–569, © 2018 INFORMS
and the best Lagrangian bound is given by vLR
maxµ∈n vLR(µ). Given H, the set of feasible solutions
of [SSP], the best Lagrangian bound can be found
by solving
max
µ
{
K · min
h1,...,H
{Q+1∑
i1
tV
i, (h) −
n∑
j1
Q∑
i1
µj xi, j, (h)
}
+
n∑
j1
µj
}
,
which is equivalent to the Lagrangian master problem:
[LMP]: max
{ n∑
j1
µj + Kθ
}
(43)
s.t
n∑
j1
Q∑
i1
µj xi, j, (h) + θ ≤
Q+1∑
i1
tV
i, (h) , ∀ h ∈ H.
(44)
Denoting with αh the dual variables associated with
constraints (44), the dual of [LMP] is the Dantzig-Wolfe
master problem:
[DMP]: min ∑
h∈H
αh
Q+1∑
i1
tV
i, (h)
s.t. ∑
h∈H
αh K;
∑
h∈H
αh
Q∑
i1
xi, j, (h) 1, ∀ j 1, . . . , n;
αh ≥ 0, ∀ h ∈ H.
Since the set H is not known beforehand, the La-
grangian bound vLR is calculated iteratively where
a relaxed version of [LMP] is solved to obtain the
Lagrange multipliers µj and then [SSP] is solved lead-
ing to a new cut in [LMP]. Note that a new cut in [LMP]
is equivalent to a new column in [DMP]. Solving the
relaxed version of [LMP] provides an upper bound on
the optimal Lagrangian bound vLR while the optimal
solution of [SSP] provides a lower bound vLR(µ). The iter-
ative approach is stopped when the upper and lower
bounds are equivalent. Being a relaxed problem, the
optimal solution of [DMP] or equivalently [LMP] pro-
vides a lower bound on the optimal solution of [OP].
5.2. Tightening the Lagrangian Bound
A main advantage for the application of the presented
Lagrangian relaxation is the decomposition of the
problem into [SSP] that is computationally less chal-
lenging to solve than [OP]. However, because of the
relaxation, the resulting Lagrangian bound is a lower
bound to [OP]. The Lagrangian bound can be tight-
ened by the addition of constraints that are redundant
to [OP] but cut a part of the feasible solutions of [SSP].
Particularly the inequalities
Q∑
i1
xi, j ≤ 1, ∀ j 1, . . . , n (45)
are valid to [OP] and improve the Lagrangian bound
when added to [SSP]. Constraints (45) indicate that each
target j should be visited by a vehicle at most once.
The Lagrangian bounds are used in a branch-
and-bound framework to obtain an optimal solution
to [OP]. As discussed next, constraints that main-
tain the decomposable structure of [SP] are used for
branching.
5.3. Branching Strategy
At each node of the branch-and-bound tree, the col-
umns matrix corresponding to [DMP] is
X
∑Q
i1 xi, 1, 1
∑Q
i1 xi, 1, 2 . . . ∑Q
i1 xi, 1, |H|
∑Q
i1 xi, 2, 1
∑Q
i1 xi, 2, 2 . . . ∑Q
i1 xi, 2, |H |
. . . . . . . . . . . .
∑Q
i1 xi, n, 1
∑Q
i1 xi, n, 2 . . . ∑Q
i1 xi, n, |H|
,
where each column h is associated with a value ¯αh that
is given by the optimal solution of [DMP] at that node.
Branching is needed when two columns h1 and h2
are associated with a fractional αh and contain the
pattern
. . . h1 . . . h2 . . .
. . . . . . . . . . . . . . . . . .
j1 . . . 1 . . . 1 . . .
. . . . . . . . . . . . . . . . . .
j2 . . . 1 . . . 0 . . .
. . . . . . . . . . . . . . . . . .
in the columns matrix X. Alternatively, when such a
pattern with fractional αh does not exist, the optimal
solution of [DMP] satisfies the integrality conditions
and a feasible solution to [OP] is found. Being a min-
imization problem, this feasible solution provides an
upper bound to [OP] and the incumbent which denotes
the best upper bound is updated. A node is fathomed
if the objective function value of [DMP] at that node
is not lower than the incumbent. As discussed in Sec-
tion 5.1, since vLR(µ) provides a lower bound, then a
node is fathomed when vLR(µ) is not lower than the
incumbent. When all the nodes in the tree are fath-
omed, the resulting incumbent is an optimal solution
to [OP].
When branching, the challenge is in devising branch-
ing constraints that can maintain the decomposable
structure of the subproblem when added. We thus pro-
pose branching constraints inspired from the Ryan-
Foster branching rules (Ryan and Foster 1981) that
have been successfully used in branch-and-price algo-
rithms with separable subproblems (Mehrotra and
Trick 1996).
Gambella et al.: The Vehicle Routing Problem with Floating Targets
INFORMS Journal on Computing, 2018, vol. 30, no. 3, pp. 554–569, © 2018 INFORMS 561
The branching constraints are based on forcing two
targets to be assigned to the same vehicle versus two
different vehicles and can be written as follows:
Q∑
i1
xk
i, j1
Q∑
i1
xk
i, j2 , ∀ k 1, . . . , K; (46)
Q∑
i1
xk
i, j1 +
Q∑
i1
xk
i, j2 ≤ 1, ∀ k 1, . . . , K. (47)
Constraints (46) impose that if targets j1 and j2 should
be picked up by the same vehicle while constraints (47)
forbid the two targets from being picked up by the
same vehicle.
In our implementation, the columns in X are ordered
with respect to the value ¯αh and those with the highest
value are checked first. If a branching pattern is found,
then X is split into two parts; the first containing all the
columns that satisfy constraints (46) while the second
containing all the columns that satisfy constraints (47).
The children nodes are then created and the master
problem [DMP] at each node is warm started with the
columns that satisfy the branching constraints that are
added to the corresponding subproblem [SSP].
6. Computational Testing
6.1. Implementation Details
In this section, we evaluate the computational per-
formance of the proposed branch-and-price algorithm
that we implemented in C. Each optimization prob-
lem is solved using CPLEX 12.6.1 with default settings.
The branch-and-price tree is explored using a depth-
first search strategy where the left node is associated to
constraints (46) and the right node is associated to con-
straints (47). The depth-first search strategy was chosen
to help finding feasible solutions of good quality early
in the tree exploration. This is in line with the search
strategy that is adopted for the same reason in the
branch-and-price algorithm of Elhedhli et al. (2011).
When solving the subproblem [SSP], constraints (30),
(31), (33), and (34) are declared as lazy constraints since
they constitute a relatively large set of constraints with
the majority of them likely not to be binding at opti-
mality. The branch-and-price approach is compared to
the direct solution of problem [OP] with constraints (4),
(5), (7), and (9) declared as lazy constraints. The results
are conducted on a Xeon E3-1220 processor clocked at
3.10 GHz with 16 GB RAM. A 7,200 seconds time limit
is imposed after which the best available solution is
reported.
6.2. Test Instances
A set of 18 randomly generated instances with varying
characteristics is used for the evaluation (the instances
can be obtained from http://www.vrp-rep.org/data
-sets/item/2016-0012.html and http://www.vrp-rep
.org/datasets/item/2016-0013.html). In particular, the
number of targets is varied between 10 and 20 and the
number of vehicles is varied between three and five.
The vehicle capacities are set to dn/Ke + 2. The home
locations of the targets are randomly generated in the
Euclidean space centered at (0, 0) and with width 50
and height 100. The initial locations of the vehicles is
set at (−20, 0) and the common destination/drop-off
location is set to (20, 0). The speed of the vehicles is
also randomly generated from the uniform distribution
U[2, 3] while the speeds of the targets are randomly
generated from the uniform distribution U[0.1, 1]. The
VRPFT with fixed line moving directions is tested on
the same 18 instances, where a random direction vector
is introduced for each target.
6.3. Initial Greedy Heuristic
At the start of the branch-and-price algorithm, a greedy
heuristic is used to initialize the incumbent. For that,
a feasible solution is easily obtained by assuming that
the pick-up order is greedily assigned to the vehicle
with the closest target ordered first. A sketch of the
greedy heuristic is as follows.
1: Initialization: Assume that all the vehicles are
currently located at the starting location O
and are empty;
2: Let S be the set of unassigned targets and
initialize S as the set of all targets;
3: Let D be a distance vector where D(j) denotes the
distance between O and the home location of
an unassigned target j and initialize D accordingly;
4: Let k be the current vehicle and initialize k to 1;
5: Let i be the number of targets served by vehicle k
and initialize i to 0;
6: while S is not empty do
7: Select target j with the minimum D(j);
8: Fix xk
i+1, j 1 in the VRPFT formulation;
9: Update S S − { j};
10: Eliminate target j from D;
11: Update i i + 1;
12: if the capacity limit of vehicle k is reached
(i.e., i Q) then
13: Update k k + 1;
14: Set i 0.
15: end if
16: end while
17: Solve the resulting VRPFT with all the binary
variables fixed to obtain the meeting locations.
Because the heuristic assigns all targets to vehicles, the
resulting VRPFT model does not contain any binary
variable and is thus a second order cone problem.
The greedy heuristic is therefore used to initialize the
incumbent with a feasible solution. The incumbent is
then updated when a better feasible solution is found
in the branch-and-price tree.
INFORMS Journal on Computing, 2018, vol. 30, no. 3, pp. 554–569, © 2018 INFORMS 561
The branching constraints are based on forcing two
targets to be assigned to the same vehicle versus two
different vehicles and can be written as follows:
Q∑
i1
xk
i, j1
Q∑
i1
xk
i, j2 , ∀ k 1, . . . , K; (46)
Q∑
i1
xk
i, j1 +
Q∑
i1
xk
i, j2 ≤ 1, ∀ k 1, . . . , K. (47)
Constraints (46) impose that if targets j1 and j2 should
be picked up by the same vehicle while constraints (47)
forbid the two targets from being picked up by the
same vehicle.
In our implementation, the columns in X are ordered
with respect to the value ¯αh and those with the highest
value are checked first. If a branching pattern is found,
then X is split into two parts; the first containing all the
columns that satisfy constraints (46) while the second
containing all the columns that satisfy constraints (47).
The children nodes are then created and the master
problem [DMP] at each node is warm started with the
columns that satisfy the branching constraints that are
added to the corresponding subproblem [SSP].
6. Computational Testing
6.1. Implementation Details
In this section, we evaluate the computational per-
formance of the proposed branch-and-price algorithm
that we implemented in C. Each optimization prob-
lem is solved using CPLEX 12.6.1 with default settings.
The branch-and-price tree is explored using a depth-
first search strategy where the left node is associated to
constraints (46) and the right node is associated to con-
straints (47). The depth-first search strategy was chosen
to help finding feasible solutions of good quality early
in the tree exploration. This is in line with the search
strategy that is adopted for the same reason in the
branch-and-price algorithm of Elhedhli et al. (2011).
When solving the subproblem [SSP], constraints (30),
(31), (33), and (34) are declared as lazy constraints since
they constitute a relatively large set of constraints with
the majority of them likely not to be binding at opti-
mality. The branch-and-price approach is compared to
the direct solution of problem [OP] with constraints (4),
(5), (7), and (9) declared as lazy constraints. The results
are conducted on a Xeon E3-1220 processor clocked at
3.10 GHz with 16 GB RAM. A 7,200 seconds time limit
is imposed after which the best available solution is
reported.
6.2. Test Instances
A set of 18 randomly generated instances with varying
characteristics is used for the evaluation (the instances
can be obtained from http://www.vrp-rep.org/data
-sets/item/2016-0012.html and http://www.vrp-rep
.org/datasets/item/2016-0013.html). In particular, the
number of targets is varied between 10 and 20 and the
number of vehicles is varied between three and five.
The vehicle capacities are set to dn/Ke + 2. The home
locations of the targets are randomly generated in the
Euclidean space centered at (0, 0) and with width 50
and height 100. The initial locations of the vehicles is
set at (−20, 0) and the common destination/drop-off
location is set to (20, 0). The speed of the vehicles is
also randomly generated from the uniform distribution
U[2, 3] while the speeds of the targets are randomly
generated from the uniform distribution U[0.1, 1]. The
VRPFT with fixed line moving directions is tested on
the same 18 instances, where a random direction vector
is introduced for each target.
6.3. Initial Greedy Heuristic
At the start of the branch-and-price algorithm, a greedy
heuristic is used to initialize the incumbent. For that,
a feasible solution is easily obtained by assuming that
the pick-up order is greedily assigned to the vehicle
with the closest target ordered first. A sketch of the
greedy heuristic is as follows.
1: Initialization: Assume that all the vehicles are
currently located at the starting location O
and are empty;
2: Let S be the set of unassigned targets and
initialize S as the set of all targets;
3: Let D be a distance vector where D(j) denotes the
distance between O and the home location of
an unassigned target j and initialize D accordingly;
4: Let k be the current vehicle and initialize k to 1;
5: Let i be the number of targets served by vehicle k
and initialize i to 0;
6: while S is not empty do
7: Select target j with the minimum D(j);
8: Fix xk
i+1, j 1 in the VRPFT formulation;
9: Update S S − { j};
10: Eliminate target j from D;
11: Update i i + 1;
12: if the capacity limit of vehicle k is reached
(i.e., i Q) then
13: Update k k + 1;
14: Set i 0.
15: end if
16: end while
17: Solve the resulting VRPFT with all the binary
variables fixed to obtain the meeting locations.
Because the heuristic assigns all targets to vehicles, the
resulting VRPFT model does not contain any binary
variable and is thus a second order cone problem.
The greedy heuristic is therefore used to initialize the
incumbent with a feasible solution. The incumbent is
then updated when a better feasible solution is found
in the branch-and-price tree.
Gambella et al.: The Vehicle Routing Problem with Floating Targets
562 INFORMS Journal on Computing, 2018, vol. 30, no. 3, pp. 554–569, © 2018 INFORMS
Table 1. Computational Results Comparing Branch and Price and CPLEX for the General VRPFT (1)–(17)
Branch and price CPLEX
Instance name Upper bound Lower bound Gap (%) CPU time (s) Upper bound Lower bound Gap (%) CPU time (s)
p_10_3_6 72.69 72.69 0 183.84 72.69 72.69 0 229.61
p_10_4_5 62.14 62.14 0 70.38 62.14 62.14 0 449.27
p_10_5_4 71.71 71.71 0 161.28 71.71 71.71 0 542.51
p_12_3_6 76.91 76.91 0 377.43 76.91 76.91 0 579.70
p_12_4_5 91.36 91.36 0 1,209.43 91.36 84.05 ∗8 >7,200
p_12_5_5 80.08 80.08 0 532.05 80.08 80.08 0 4,107.24
p_14_3_7 84.47 84.47 0 3,841.94 84.47 84.47 0 6,961.36
p_14_4_6 97.62 97.62 0 5,131.43 103.97 90.45 13 >7,200
p_14_5_5 80.18 80.18 0 377.12 80.18 73.77 ∗8 >7,200
p_16_3_8 181.58 78.08 57 >7,200 85.84 78.97 8 >7,200
p_16_4_6 75.85 75.85 0 6,635.41 76.71 75.18 2 >7,200
p_16_5_6 91.68 91.68 0 6,084.35 96.7 64.79 33 >7,200
p_18_3_8 217.47 97.86 55 >7,200 132.58 86.18 35 >7,200
p_18_4_7 80.68 75.03 7 >7,200 87.64 60.47 31 >7,200
p_18_5_6 76.18 76.18 0 1,132.36 78.73 59.05 25 >7,200
p_20_3_9 193.88 50.41 74 >7,200 104.74 67.03 36 >7,200
p_20_4_7 216.63 106.15 51 >7,200 127.02 83.83 34 >7,200
p_20_5_6 128.35 114.23 11 >7,200 133.24 97.27 27 >7,200
∗Indicates that the upper bound is the optimal solution however the gap is a result of the lower bound.
6.4. Results
This section presents two sets of results, the first
comparing the performance of CPLEX to the pro-
posed branch-and-price algorithm in solving the gen-
eral VRPFT (1)–(17) while the second set of results
presents the same comparison for the VRPFT with
fixed line moving directions that is presented in Sec-
tion 3.2. We note that the results that are presented in
this section do not include the valid inequalities that
are discussed in Section 4. The impact of the valid
inequalities is evaluated next in Section 6.5.
Tables 1 and 2 illustrate the performance of the pro-
posed branch-and-price compared to the performance
of CPLEX for VRPFT and VRPFT with fixed line mov-
ing directions, while Tables 3 and 4 provide the details
of the performance of each of the components of the
branch-and-price algorithm. Particularly, the following
details are provided:
• Instance Name: p_t_v_c indicates an instance
with t targets, v vehicles, and c vehicle capacity.
• Upper Bound: Best upper bound found by the
algorithm.
• Lower Bound: Best lower bound found by the
algorithm.
• Gap (%): Percentage gap calculated as (Upper
Bound − Lower Bound)/Upper Bound.
• CPU Time (s): Total computational CPU time in
seconds.
• Number of Nodes: Total number of nodes ex-
plored by the branch-and-price algorithm.
• Iterations: Total number of iterations at the root
node.
• CPU Master Problem: Total CPU time spent on
solving the master problems at the root node.
• CPU Subproblem: Total CPU time spent on solv-
ing the subproblems at the root node.
• Avg. Iterations: Average number of iterations at
each of the nodes of the branch-and-price tree exclud-
ing the root node.
• Avg. CPU Master Problem: Average Total CPU
time spent on solving the master problems at each of
the nodes of the branch-and-price tree excluding the
root node.
• Avg. CPU Subproblem: Average Total CPU time
spent on solving the subproblems at each of the nodes
of the branch-and-price tree excluding the root node.
As shown in Tables 1 and 2, the proposed branch-
and-price algorithm outperforms CPLEX for the major-
ity of the tested instances. For VRPFT (Table 1), branch-
and-price solved 12 instances to optimality within
the time limit while CPLEX solved five instances.
For the VRPFT with fixed line moving directions
(Table 2), branch and price solved 14 instances to opti-
mality while CPLEX solved seven instances. For the
instances where the time limit is reached, we notice
that branch and price tends to find a better lower
bound than CPLEX thus highlighting the advantage
of column generation (p_18_3_8, p_18_4_7, p_20_4_7
and p_20_5_6 in Table 1 and p_18_3_8, p_18_4_7,
p_20_3_9 and p_20_5_6 in Table 2). On the other hand,
CPLEX found a better upper bound than the pro-
posed branch and price for five instances (p_16_3_8,
p_18_3_8, p_20_3_9, and p_20_4_7 in Table 1 and
p_20_3_9 in Table 2). The better upper bound in such
cases is expected because of the capabilities of CPLEX
562 INFORMS Journal on Computing, 2018, vol. 30, no. 3, pp. 554–569, © 2018 INFORMS
Table 1. Computational Results Comparing Branch and Price and CPLEX for the General VRPFT (1)–(17)
Branch and price CPLEX
Instance name Upper bound Lower bound Gap (%) CPU time (s) Upper bound Lower bound Gap (%) CPU time (s)
p_10_3_6 72.69 72.69 0 183.84 72.69 72.69 0 229.61
p_10_4_5 62.14 62.14 0 70.38 62.14 62.14 0 449.27
p_10_5_4 71.71 71.71 0 161.28 71.71 71.71 0 542.51
p_12_3_6 76.91 76.91 0 377.43 76.91 76.91 0 579.70
p_12_4_5 91.36 91.36 0 1,209.43 91.36 84.05 ∗8 >7,200
p_12_5_5 80.08 80.08 0 532.05 80.08 80.08 0 4,107.24
p_14_3_7 84.47 84.47 0 3,841.94 84.47 84.47 0 6,961.36
p_14_4_6 97.62 97.62 0 5,131.43 103.97 90.45 13 >7,200
p_14_5_5 80.18 80.18 0 377.12 80.18 73.77 ∗8 >7,200
p_16_3_8 181.58 78.08 57 >7,200 85.84 78.97 8 >7,200
p_16_4_6 75.85 75.85 0 6,635.41 76.71 75.18 2 >7,200
p_16_5_6 91.68 91.68 0 6,084.35 96.7 64.79 33 >7,200
p_18_3_8 217.47 97.86 55 >7,200 132.58 86.18 35 >7,200
p_18_4_7 80.68 75.03 7 >7,200 87.64 60.47 31 >7,200
p_18_5_6 76.18 76.18 0 1,132.36 78.73 59.05 25 >7,200
p_20_3_9 193.88 50.41 74 >7,200 104.74 67.03 36 >7,200
p_20_4_7 216.63 106.15 51 >7,200 127.02 83.83 34 >7,200
p_20_5_6 128.35 114.23 11 >7,200 133.24 97.27 27 >7,200
∗Indicates that the upper bound is the optimal solution however the gap is a result of the lower bound.
6.4. Results
This section presents two sets of results, the first
comparing the performance of CPLEX to the pro-
posed branch-and-price algorithm in solving the gen-
eral VRPFT (1)–(17) while the second set of results
presents the same comparison for the VRPFT with
fixed line moving directions that is presented in Sec-
tion 3.2. We note that the results that are presented in
this section do not include the valid inequalities that
are discussed in Section 4. The impact of the valid
inequalities is evaluated next in Section 6.5.
Tables 1 and 2 illustrate the performance of the pro-
posed branch-and-price compared to the performance
of CPLEX for VRPFT and VRPFT with fixed line mov-
ing directions, while Tables 3 and 4 provide the details
of the performance of each of the components of the
branch-and-price algorithm. Particularly, the following
details are provided:
• Instance Name: p_t_v_c indicates an instance
with t targets, v vehicles, and c vehicle capacity.
• Upper Bound: Best upper bound found by the
algorithm.
• Lower Bound: Best lower bound found by the
algorithm.
• Gap (%): Percentage gap calculated as (Upper
Bound − Lower Bound)/Upper Bound.
• CPU Time (s): Total computational CPU time in
seconds.
• Number of Nodes: Total number of nodes ex-
plored by the branch-and-price algorithm.
• Iterations: Total number of iterations at the root
node.
• CPU Master Problem: Total CPU time spent on
solving the master problems at the root node.
• CPU Subproblem: Total CPU time spent on solv-
ing the subproblems at the root node.
• Avg. Iterations: Average number of iterations at
each of the nodes of the branch-and-price tree exclud-
ing the root node.
• Avg. CPU Master Problem: Average Total CPU
time spent on solving the master problems at each of
the nodes of the branch-and-price tree excluding the
root node.
• Avg. CPU Subproblem: Average Total CPU time
spent on solving the subproblems at each of the nodes
of the branch-and-price tree excluding the root node.
As shown in Tables 1 and 2, the proposed branch-
and-price algorithm outperforms CPLEX for the major-
ity of the tested instances. For VRPFT (Table 1), branch-
and-price solved 12 instances to optimality within
the time limit while CPLEX solved five instances.
For the VRPFT with fixed line moving directions
(Table 2), branch and price solved 14 instances to opti-
mality while CPLEX solved seven instances. For the
instances where the time limit is reached, we notice
that branch and price tends to find a better lower
bound than CPLEX thus highlighting the advantage
of column generation (p_18_3_8, p_18_4_7, p_20_4_7
and p_20_5_6 in Table 1 and p_18_3_8, p_18_4_7,
p_20_3_9 and p_20_5_6 in Table 2). On the other hand,
CPLEX found a better upper bound than the pro-
posed branch and price for five instances (p_16_3_8,
p_18_3_8, p_20_3_9, and p_20_4_7 in Table 1 and
p_20_3_9 in Table 2). The better upper bound in such
cases is expected because of the capabilities of CPLEX
Gambella et al.: The Vehicle Routing Problem with Floating Targets
INFORMS Journal on Computing, 2018, vol. 30, no. 3, pp. 554–569, © 2018 INFORMS 563
Table 2. Computational Results Comparing Branch and Price and CPLEX for VRPFT with Fixed Line Direction
Branch and price CPLEX
Instance name Upper bound Lower bound Gap (%) CPU time (s) Upper bound Lower bound Gap (%) CPU time (s)
p_10_3_6 85.51 85.51 0 31.40 85.51 85.51 0 154.09
p_10_4_5 72.06 72.06 0 20.56 72.06 72.06 0 104.20
p_10_5_4 83.33 83.33 0 25.95 83.33 83.33 0 99.32
p_12_3_6 94.55 94.55 0 60.57 94.55 94.55 0 111.76
p_12_4_5 109.34 109.34 0 137.00 109.34 109.34 0 3,510.18
p_12_5_5 91.55 91.55 0 79.52 91.55 91.55 0 2,669.57
p_14_3_7 101.43 101.43 0 361.97 101.44 101.44 0 2,676.76
p_14_4_6 105.19 105.19 0 1,109.85 113.99 101.45 11 >7,200
p_14_5_5 89.31 89.31 0 104.39 89.97 82.77 8 >7,200
p_16_3_8 100.63 100.63 0 3,035.48 100.63 93.59 ∗7 >7,200
p_16_4_6 97.91 97.91 0 1,577.55 111.85 82.77 26 >7,200
p_16_5_6 105.37 105.37 0 401.00 124.07 98.02 21 >7,200
p_18_3_8 167.57 140.76 16 >7,200 198.62 101.3 49 >7,200
p_18_4_7 85.96 84.24 2 >7,200 99.84 69.89 30 >7,200
p_18_5_6 97.93 97.93 0 1,333.93 110.27 77.19 30 >7,200
p_20_3_9 248.08 81.87 67 >7,200 159.38 74.91 53 >7,200
p_20_4_7 128.94 128.94 0 4,750.29 169.41 94.87 44 >7,200
p_20_5_6 137.36 127.74 7 >7,200 187.12 104.79 44 >7,200
∗Indicates that the upper bound is the optimal solution however the gap is a result of the lower bound.
in finding good feasible solutions through heuristics.
Branch and price also found a better upper bound
than CPLEX for five instances (p_18_4_7 and p_20_5_6
in Table 1 and p_18_3_8, p_18_4_7, and p_20_5_6 in
Table 2).
Table 3. Details of the Branch-and-Price Performance for the General VRPFT (1)–(17)
Root node Other nodes†
Instance Number CPU master CPU Avg. Avg. CPU Avg. CPU
name of nodes Iterations problem subproblem iterations master problem subproblem
p_10_3_6 17 29 <0.01 60.18 5 0.02 7.71
p_10_4_5 1 37 0.10 70.26 — — —
p_10_5_4 41 30 <0.01 25.26 4 <0.01 3.40
p_12_3_6 1 63 <0.01 377.39 — — —
p_12_4_5 147 27 <0.01 62.71 4 <0.01 7.85
p_12_5_5 67 39 <0.01 88.7 5 <0.01 6.72
p_14_3_7 1 109 0.02 3,841.8 — — —
p_14_4_6 157 51 <0.01 532.1 6 <0.01 29.48
p_14_5_5 15 50 <0.01 143.99 7 <0.01 16.65
p_16_3_8 1 97 0.11 >7,200 — — —
p_16_4_6 83 66 <0.01 1,182.2 7 <0.01 66.49
p_16_5_6 119 51 0.03 484.03 7 <0.01 47.45
p_18_3_8 1 67 0.01 >7,200 — — —
p_18_4_7 39 62 <0.01 2,275.28 7 <0.01 134.43
p_18_5_6 1 81 0.01 1,132.23 — — —
p_20_3_9 1 39 <0.01 >7,200 — — —
p_20_4_7 1 103 0.02 >7,200 — — —
p_20_5_6 187 77 0.01 2,254.2 5 <0.01 27.35
†Indicates the average results over all the nodes except the root node in the branch-and-price tree.
—Indicates that the branch and price stopped at the root node.
The comparison between the results that are shown
in Tables 1 and 2 also reveal that the VRPFT with
fixed line direction is computationally less challeng-
ing to solve than the general VRPFT. As indicated in
Section 3.2, this is because of the need of additional
INFORMS Journal on Computing, 2018, vol. 30, no. 3, pp. 554–569, © 2018 INFORMS 563
Table 2. Computational Results Comparing Branch and Price and CPLEX for VRPFT with Fixed Line Direction
Branch and price CPLEX
Instance name Upper bound Lower bound Gap (%) CPU time (s) Upper bound Lower bound Gap (%) CPU time (s)
p_10_3_6 85.51 85.51 0 31.40 85.51 85.51 0 154.09
p_10_4_5 72.06 72.06 0 20.56 72.06 72.06 0 104.20
p_10_5_4 83.33 83.33 0 25.95 83.33 83.33 0 99.32
p_12_3_6 94.55 94.55 0 60.57 94.55 94.55 0 111.76
p_12_4_5 109.34 109.34 0 137.00 109.34 109.34 0 3,510.18
p_12_5_5 91.55 91.55 0 79.52 91.55 91.55 0 2,669.57
p_14_3_7 101.43 101.43 0 361.97 101.44 101.44 0 2,676.76
p_14_4_6 105.19 105.19 0 1,109.85 113.99 101.45 11 >7,200
p_14_5_5 89.31 89.31 0 104.39 89.97 82.77 8 >7,200
p_16_3_8 100.63 100.63 0 3,035.48 100.63 93.59 ∗7 >7,200
p_16_4_6 97.91 97.91 0 1,577.55 111.85 82.77 26 >7,200
p_16_5_6 105.37 105.37 0 401.00 124.07 98.02 21 >7,200
p_18_3_8 167.57 140.76 16 >7,200 198.62 101.3 49 >7,200
p_18_4_7 85.96 84.24 2 >7,200 99.84 69.89 30 >7,200
p_18_5_6 97.93 97.93 0 1,333.93 110.27 77.19 30 >7,200
p_20_3_9 248.08 81.87 67 >7,200 159.38 74.91 53 >7,200
p_20_4_7 128.94 128.94 0 4,750.29 169.41 94.87 44 >7,200
p_20_5_6 137.36 127.74 7 >7,200 187.12 104.79 44 >7,200
∗Indicates that the upper bound is the optimal solution however the gap is a result of the lower bound.
in finding good feasible solutions through heuristics.
Branch and price also found a better upper bound
than CPLEX for five instances (p_18_4_7 and p_20_5_6
in Table 1 and p_18_3_8, p_18_4_7, and p_20_5_6 in
Table 2).
Table 3. Details of the Branch-and-Price Performance for the General VRPFT (1)–(17)
Root node Other nodes†
Instance Number CPU master CPU Avg. Avg. CPU Avg. CPU
name of nodes Iterations problem subproblem iterations master problem subproblem
p_10_3_6 17 29 <0.01 60.18 5 0.02 7.71
p_10_4_5 1 37 0.10 70.26 — — —
p_10_5_4 41 30 <0.01 25.26 4 <0.01 3.40
p_12_3_6 1 63 <0.01 377.39 — — —
p_12_4_5 147 27 <0.01 62.71 4 <0.01 7.85
p_12_5_5 67 39 <0.01 88.7 5 <0.01 6.72
p_14_3_7 1 109 0.02 3,841.8 — — —
p_14_4_6 157 51 <0.01 532.1 6 <0.01 29.48
p_14_5_5 15 50 <0.01 143.99 7 <0.01 16.65
p_16_3_8 1 97 0.11 >7,200 — — —
p_16_4_6 83 66 <0.01 1,182.2 7 <0.01 66.49
p_16_5_6 119 51 0.03 484.03 7 <0.01 47.45
p_18_3_8 1 67 0.01 >7,200 — — —
p_18_4_7 39 62 <0.01 2,275.28 7 <0.01 134.43
p_18_5_6 1 81 0.01 1,132.23 — — —
p_20_3_9 1 39 <0.01 >7,200 — — —
p_20_4_7 1 103 0.02 >7,200 — — —
p_20_5_6 187 77 0.01 2,254.2 5 <0.01 27.35
†Indicates the average results over all the nodes except the root node in the branch-and-price tree.
—Indicates that the branch and price stopped at the root node.
The comparison between the results that are shown
in Tables 1 and 2 also reveal that the VRPFT with
fixed line direction is computationally less challeng-
ing to solve than the general VRPFT. As indicated in
Section 3.2, this is because of the need of additional